import java.awt.Color;
import java.util.HashMap;

/** Class for segmenting a grayscale image into
 * contiguous components by brightness.*/
public class Segmentation {
	
	/** Loads and segments the image at the given path.
	 * 
	 * @param fileName the path to the image to load.
	 */
	public Segmentation(String fileName) {		
		/* No room for more informative input validation
		 * than that already provided by DisplayImage */
		
		image = new DisplayImage(fileName);
		
		int height = image.height();
		int width = image.width();
		
		unions = new UnionFind(height * width);

		/* Attempt to connect each pixel to up to two neighbors,
		 * one horizontally adjacent, one vertically.*/
		for (int y = 0; y < height - 1; ++y) {
			for (int x = 0; x < width - 1; ++x) {
				connect(x,y,x,y+1);
				connect(x,y,x+1,y);
			}
			
			// Don't forget the last pixel of each horizontal line
			connect(width - 1, y, width - 1, y + 1);							
		}
		
		// Nor the final horizontal line
		for (int x = 0; x < width - 1; ++x)
			connect(x, height - 1, x + 1, height - 1);				
	}
	
	/** Given two pixels in the image, compares their brightness levels,
	 * merges their components if both are on the same side of the
	 * bright/dark threshold.
	 * 
	 * @param x1 x coordinate of first pixel.
	 * @param y1 y coordinate of first pixel.
	 * @param x2 x coordinate of second pixel.
	 * @param y2 y coordinate of second pixel.
	 */
	public void connect(int x1, int y1, int x2, int y2) {
		/* No room for more informative input validation
		 * than that already provided by DisplayImage */
		
		 if (image.isOn(x1, y1) == image.isOn(x2, y2) &&
				 (!areConnected(x1, y1, x2, y2)))			 			 
			 // Brightness match, pixels not already connected. Connect them.
			 unions.union(unions.find(getIndex(x1,y1)),
					 unions.find(getIndex(x2,y2)));
	}
	
	/** Returns true if two given pixels in the image share a component.
	 * 
	 * @param x1 x coordinate of first pixel.
	 * @param y1 y coordinate of first pixel.
	 * @param x2 x coordinate of second pixel.
	 * @param y2 y coordinate of second pixel.
	 * 
	 * @return true if pixels (x1, y1) and (x2, y2) are in the same component.
	 */
	public boolean areConnected(int x1, int y1, int x2, int y2) {
		return unions.find(getIndex(x1,y1)) == unions.find(getIndex(x2,y2));
	}
	
	/** Returns the number of components (disjoint segments) in the image.
	 * 
	 * @return the number of components (disjoint segments) in the image.
	 */
	public int getNumComponents() {
		return unions.getNumSets();
	}
	
	/** Returns a version of the image recolored to highlight components.
	 * 
	 * @return a version of the image recolored to highlight components.
	 */
	public DisplayImage getComponentImage() {
		int numComponents = getNumComponents();
		int width = image.width();
		int height = image.height();
		
		DisplayImage result = new DisplayImage(width, height);
		
		// Generate palette
		Color[] colors = new Color[numComponents];
		
		colors[0] = new Color(0,0,100);
		for (int c = 1; c< numComponents; ++c)
			colors[c] = new Color((int)(Math.random() * MAX_COLOR));
		
		// Map component representatives to colors
		HashTable colorMap = new HashTable(numComponents * 2);
		int[] representatives = unions.getRepresentatives();
		
		for (int i = 0; i < numComponents; ++i)
			colorMap.put(representatives[i], i);				
				
		// Pixel-by-pixel image creation
		for (int x = 0; x < width; ++x)
			for (int y = 0; y < height; ++y) {
				// Find pixel's component and its color, add to output image
				int currentRep = unions.find(getIndex(x,y));
				 
				result.set(x, y, colors[colorMap.get(currentRep)]);
			}
		
		return result;
	}
	
	/** Given a pixel in the image, returns the value of its corresponding
	 * element in the "unions" field.
	 * 
	 * @param x the x coordinate of the pixel.
	 * @param y the y coordinate of the pixel.
	 * 
	 * @return the pixel's value in field unions.
	 */
	private int getIndex(int x, int y) {
		return (x + image.width() * y) + 1;
	}
	
	private DisplayImage image;
	
	private UnionFind unions;
	
	private final int MAX_COLOR = 0xffffff;
}
